package ru.averta.notes.service.math;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import ru.averta.notes.service.search.MistakeLettersDetector;

/**
 * <code>EditDistance</code>
 * <p/>
 * Реализуем алгоритм Damerau Levenshtein
 * <p/>
 * http://habrahabr.ru/blogs/algorithm/123320/
 * http://www.bericotechnologies.com/node/139
 * http://coderlife.ru/progr/rasstoyanie-mezhdu-strokami-mif-ili-realnost.html
 *
 * @author fedor.belov (fedor.belov@mail.ru)
 *         Date: 06.09.11 14:04
 */

@Service
public class EditDistance {

    //Определяем буквы, в которых вероятность ошибки велика
    @Autowired private MistakeLettersDetector mistakeLettersDetecter;

    static final int VALUE_OF_EXCHANGE = 1; // Цена обмена символа строки t[se]t -> test
    static final int VALUE_OF_DELETE = 2; // Цена удаления символа строки testt -> test //TODO уменьшить цену удаления повторной буквы (поошел)
    static final int VALUE_OF_INSERT = 2; // Цена вставки символа строки  tet -> test
    static final byte PREFIX_DISTANCE_FACTOR = 1;

    static final byte FLAG_INSERTED = 1;
    static final byte FLAG_DELETED = 2;
    static final byte FLAG_CHANGED = 3;
    static final byte FLAG_EXCHANGED = 4;
    static final byte FLAG_SAME = 0;


    public DistanceResult getDamerauLevenshteinDistanceResult(String source, String target) {

        //Проверяем, что строки не пустые
        if (source.isEmpty() || target.isEmpty()) return null;

        int sourceSize = source.length();
        int targetSize = target.length();

        char[] sourceArray = source.toCharArray();
        char[] targetArray = target.toCharArray();

        //Инициализируем матрицу расстояний
        int[] minValue;
        byte[][] changeMatrix = new byte[sourceSize + 1][targetSize + 1];
        int[][] distanceMatrix = new int[sourceSize + 1][targetSize + 1];

        //Увеличиваем цену добавления / удаления первой буквы (умножая на 2)
        for (int i = 0; i <= sourceSize; i++) {
            distanceMatrix[i][0] = i*VALUE_OF_DELETE; //TODO *2
            changeMatrix[i][0] = FLAG_DELETED;
        }
        for (int j = 0; j <= targetSize; j++) {
            distanceMatrix[0][j] = j*VALUE_OF_INSERT; //TODO *2
            changeMatrix[0][j] = FLAG_INSERTED;
        }

        //Заполняем матрицу
        for (int i = 1; i <= sourceSize; i++) {
            for (int j = 1; j <= targetSize; j++) {

                // Вычисляем стоимость замены символа
                int valueOfReplace = getValueOfReplace(sourceArray[i - 1], targetArray[j - 1]);

                minValue = minimum(
                        distanceMatrix[i - 1][j] + VALUE_OF_DELETE,
                        distanceMatrix[i][j - 1] + VALUE_OF_INSERT,
                        distanceMatrix[i - 1][j - 1] + valueOfReplace
                );

                distanceMatrix[i][j] = minValue[0];

                //Заполним матрицу изменений
                if (minValue[1] == 0) {
                    changeMatrix[i][j] = FLAG_DELETED;
                } else if (minValue[1] == 1) {
                    changeMatrix[i][j] = FLAG_INSERTED;
                } else if (minValue[1] == 2 && valueOfReplace > 0) {
                    changeMatrix[i][j] = FLAG_CHANGED;
                } else {
                    changeMatrix[i][j] = FLAG_SAME;
                }

                // Учтем обмен
                if (i > 1 && j > 1 &&
                        sourceArray[i - 1] == targetArray[j - 2] &&
                        sourceArray[i - 2] == targetArray[j - 1]) {

                    minValue = minimum(distanceMatrix[i - 2][j - 2] + VALUE_OF_EXCHANGE, distanceMatrix[i][j]);
                    distanceMatrix[i][j] = minValue[0];

                    if (minValue[1] == 0) changeMatrix[i][j] = FLAG_EXCHANGED;  //Произошла замена
                }
            }
        }

        // Возьмем минимальное префиксное расстояние
        int min_dist = distanceMatrix[sourceSize][0];
        for (int i = 1; i <= targetSize; ++i) {
            if (distanceMatrix[sourceSize][i] < min_dist)
                min_dist = distanceMatrix[sourceSize][i];
        }

        return new DistanceResult(sourceArray, targetArray, distanceMatrix, changeMatrix, PREFIX_DISTANCE_FACTOR);
    }


    /**
     * Возвращает стоимость замены символа source на target
     *
     * @param source
     * @param target
     * @return
     */
    int getValueOfReplace(char source, char target) {
        if (source == target) {
            return 0;
        } else {
            if (mistakeLettersDetecter.isMistakeLetters(source, target)) {
                //Вероятность такой ошибки велика
                return 1;
            } else {
                //Вероятность такой ошибки невелика
                return 2;
            }
        }
    }


    /**
     * Calculate the minimum value from an array of values.
     *
     * @param values Array of values.
     * @return minimum value of the provided set.
     */
    private static int[] minimum(int... values) {

        //Hopefully, everything should be smaller
        //than the max int value!
        int currentMinimum = Integer.MAX_VALUE;
        byte minCount = -1;
        byte j = 0;

        //Iterate over all provided values
        for (int value : values) {

            //Take the minimum value between the current
            //minimum and the current value of the
            //iteration
            if (value < currentMinimum) {
                currentMinimum = value;
                minCount = j;
            }

            j++;
        }

        //return the minimum value.
        return new int[]{currentMinimum, minCount};
    }

}
